package zwyarraylist;

import java.util.ArrayList;
import java.util.List;

/**
* @ClassName: BinarySearch 
* @Description:  二分查找研究
* @author zhaoweiyong  hj 
* @date x年y月z日 
 */
public class BinarySearch {
	
	public static void main(String[] args) {
		//取中间位置的索引 >>>1
		middleTest(0,5);
		long start = System.currentTimeMillis();
		int result = 0;
		int value = Integer.MAX_VALUE;
		for(int i=0; i< value; i++){
			result = value / 2;
			
		}
		long end = System.currentTimeMillis();
		System.out.println("除法/用时:" + (end-start) +", 结果:"+result);
		
		
		
//		List<Integer> integerList = new ArrayList<Integer>();
//		for(int i=0; i< 100; i++){
//			integerList.add(i*100);
//		}
//		int result = indexedBinarySearch(integerList, 5000);
//		System.out.println(result);
	}

	/**
	* 取中间位置的索引
	* @title: middleTest
	* @param low
	* @param high 
	* @Author: zhaoweiyong
	* @Date: 2017年6月7日下午1:51:28
	 */
	private static void middleTest(int low, int high) {
		//中间位置 公式 (start + end) / 2
		System.out.println((low + high) >>> 1);
	}

	private static <T> int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
		int low = 0;
		int high = list.size() - 1;
		
		while (low <= high) {
			int mid = (low + high) >>> 1;
			Comparable<? super T> midVal = list.get(mid);
			int cmp = midVal.compareTo(key);

			if (cmp < 0)
				low = mid + 1;
			else if (cmp > 0)
				high = mid - 1;
			else
				return mid;
		}
		//low > high 的唯一情况list.size == 0
		//可以直接写成return -1;
		return -(low + 1); 
	}
}
